from collections import deque
# from copy import deepcopy
import random as rd
from tkinter.constants import NO
import numpy as np
from numpy.core.numeric import Inf
from numpy.lib.arraysetops import isin

# from win32api import SetFileAttributes, Sleep
from tkGraph import DrawGraph
from trees import FibHeap, NormalTree, TreeNode, Forest
from tktree import DrawTreeByLink, DrawForest

INF = 999999

class Vertice(object):
	def __init__(self, ID=-1):
		super().__init__()
		self.color = 'white'
		self.ID = ID
		self.content = str(ID)
		self.adj = []
		self.drawRect = ()
		self.drawXY = ()
		self.dist = dict()
		self.pred = None
		self.linkedV = []
		self.pTreeNode = None
		self.dt = self.ft = 0  # discovering time and finish time
		self.adjMark = 0
		self.edgeType = dict()
		self.inTreeID = None
		self.mark = False
		self.dsSet = None
		self.key = INF

	def __str__(self):
		return str(self.ID)

class Edge(tuple):
	def __init__(self, vpair):
		super().__init__()
		self.pair = vpair
		self.w = INF
		self.color = 'red'
		self.thickness = 1

	def __str__(self):
		return str((self[0].ID, self[1].ID))+','+str(self.w)+','+self.color

class Graph(object):
	def __init__(self, directG=True, acylic=True):
		super().__init__()
		self.V = []
		self.E = dict()
		self.directG = directG
		self.acylicG = acylic
		self.adjMT = None
		self.predMT = None

	def convert(self):  #between adj list and adj matrix
		N = len(self.V)
		objINF = SingletonINF()
		if self.adjMT is None:
			self.adjMT = np.ndarray((N,N), dtype=SingletonINF)
			self.adjMT.fill(objINF)
			np.fill_diagonal(self.adjMT, 0)
			self.predMT = np.ndarray((N,N), dtype=int)
			self.predMT.fill(objINF)
			for e in self.E:
				r, c = e[0].ID, e[1].ID
				self.adjMT[r, c] = self.E[e].w
				self.predMT[r, c] = r
		elif len(self.E) == 0:
			for r in range(N):
				for c in range(N):
					u, v = self.findbyID(r), self.findbyID(c)
					e = Edge((u,v))
					e.w = self.adjMT[r, c]
					self.E[(u,v)] = e
					u.adj.append(v)

	def findbyID(self, id):
		if id < len(self.V) and self.V[id].ID == id:
			return self.V[id]
		else:
			for v in self.V:
				if v.ID == id:
					return self.V[id]

	def randomGraph(self, countV, countE, seed = 0):
		rd.seed(seed)
		# rd.seed(6)
		for i in range(countV):
			v = Vertice(i)
			self.V.append(v)
		i = 0
		while i < countE:
			v1, v2 = tuple(rd.sample(self.V,2))
			e = Edge((v1, v2))
			e.w = rd.randint(1, 15)
			if (v1,v2) not in self.E:
				self.E[(v1,v2)] = e
				v1.adj.append(v2)
				if self.directG == False:
					e2 = Edge((v2, v1))
					e2.w = e.w
					self.E[(v2,v1)] = e2
					v2.adj.append(v1)
				i += 1
		self.E = dict(sorted(self.E.items(),key=lambda x:x[1].pair[0].ID))
		self.handle = self.V[0]

	def randomGraph_MF(self, countV, countE, seed = 0):
		rd.seed(seed)
		for i in range(countV):
			v = Vertice(i)
			self.V.append(v)
		self.source, self.sink = self.V[0], self.V[-1]
		i = 0
		while i < countE:
			v1, v2 = tuple(rd.sample(self.V,2))
			if (v1,v2) not in self.E and v2 != self.source and v1 != self.sink and (v2,v1) not in self.E:
				e = Edge((v1, v2))
				e.c = rd.randint(1, 15) * 2
				e.f = 0
				e.r = e.c
				e.w = str(e.f) + '/' + str(e.c)  #name it to e.w for drawing convenience
				self.E[(v1,v2)] = e
				v1.adj.append(v2)
				i += 1
		self.E = dict(sorted(self.E.items(),key=lambda x:x[1].pair[0].ID))

	def BFS(self, startID):
		for v in self.V:
			v.color = 'white'
			v.pred = None
		start = self.V[startID]
		start.linkedV = []
		qu = deque()
		qu.append(start)
		start.dist[start.ID] = 0
		while len(qu) != 0:
			u = qu.popleft()
			for v in u.adj:
				if v.color == 'white':
					qu.append(v)
					start.dist[v.ID] = start.dist[u.ID] + 1
					v.color = 'gray'
					v.pred = u
			u.color = 'green'
			start.linkedV.append(u)

	def DFS(self, reverseEdge=False):  # reverse is true for strongly connected component calculation
		self.V.sort(key=lambda x:x.ft, reverse=True)
		if reverseEdge == True:
			for v in self.V:
				v.adj = []
				v.adjMark = 0
			for u,v in self.E:
				v.adj.append(u)   # convert the edge direction
		for v in self.V:
			v.color = 'white'
			v.pred = None
		# use stack instead of recursive solution:
		time = 0
		for start in self.V:
			if start.color == 'white':
				time += 1
				start.dt = time
				start.color = 'gray'
				start.inTreeID = start.ID
				qu = deque()
				qu.append(start)
				while len(qu) != 0:
					u = qu[-1]
					while True: 
						if u.adjMark < len(u.adj):
							v = u.adj[u.adjMark]
							if v.color == 'white':
								v.color = 'gray'
								v.pred = u
								v.inTreeID = start.ID
								time += 1
								v.dt = time
								qu.append(v)
								u.edgeType[v.ID] = 'T'
								u.adjMark += 1
								u = v
							else:
								u.adjMark += 1
								if v.color == 'gray':
									u.edgeType[v.ID] = 'B'
								elif v.color == 'green':
									if u.inTreeID == v.inTreeID:
										u.edgeType[v.ID] = 'F'
									else:
										u.edgeType[v.ID] = 'C'
						else:
							u.color = 'green'
							time += 1
							u.ft = time
							# u.content = str(u.ID) + ':' + str((u.dt,u.ft))
							qu.pop()
							break
		if reverseEdge == True:
			for v in self.V:
				v.adj = []
				v.adjMark = 0
			for u,v in self.E:
				u.adj.append(v)  # restore the real edges
		if reverseEdge == False:
			for u,v in self.E:
				if u.inTreeID == v.inTreeID:
					self.E[(u,v)].color = 'blue'
			self.V.sort(key=lambda x:x.ID)
		frt = self.graph2Forest()
		return frt

	def DFS_singleSource(self, start=None):
		for v in self.V:
			v.mark = False
		topoSorted = deque()
		if start == None:
			start = self.V[0]
		self._recDFS_singleSource(start, topoSorted)
		return topoSorted
	
	def _recDFS_singleSource(self, u, topoSorted):
		u.mark = True
		if len(u.adj) == 0:
			topoSorted.appendleft(u)
		else:
			for v in u.adj:
				if v.mark != True:
					self._recDFS_singleSource(v, topoSorted)
			topoSorted.appendleft(u)
		
	def graph2Tree(self, startID=None):
		if startID == None:
			start = self.V[0]
		else: start = self.V[startID]
		for v in self.V:
			v.pTreeNode = None
		t = NormalTree()
		start.pTreeNode = t._root = TreeNode(content=start.content,childType=[])
		t._root.parent = None
		for v in self.V:
			u = v.pred
			if u != None:
				if v.pTreeNode == None:
					n = v.pTreeNode = TreeNode(content=v.content,childType=[])
				else: n = v.pTreeNode
				if u.pTreeNode == None:
					p = u.pTreeNode = TreeNode(content=u.content,childType=[]) 
				else:
					p = u.pTreeNode
				p.children.append(n)
				n.parent = p
		t._updateBFTLink()
		t._updateTreeInfo()
		return t

	def graph2Forest(self):
		frt = Forest()
		for v in self.V:
			v.pTreeNode = None
		for v in self.V:
			if v.pTreeNode == None:
				v.pTreeNode = TreeNode(content=v.content, childType=[])
			if v.pred == None:
				t = NormalTree()
				t._root = v.pTreeNode
				frt.append(t)
			else:
				u = v.pred
				if u.pTreeNode == None:
					u.pTreeNode = TreeNode(content=u.content, childType=[])
				v.pTreeNode.parent = u.pTreeNode
				u.pTreeNode.children.append(v.pTreeNode)
		for t in frt:
			t._updateBFTLink()
			t._updateTreeInfo()			
		return frt

	def scc(self):
		frt = self.DFS(reverseEdge=True)
		draw = DrawForest(frt)
		frt = self.DFS(reverseEdge=False)
		draw = DrawForest(frt)

	def mst_K(self):
		self.E = dict(sorted(self.E.items(), key=lambda x:x[1].w))
		for u,v in self.E:
			if u.dsSet == None:
				u.dsSet = DisjointSet(u)
			if v.dsSet == None:
				v.dsSet = DisjointSet(v)
			if u.dsSet.rep != v.dsSet.rep:
				u.dsSet.union(v.dsSet)
				self.E[(u,v)].color = self.E[(v,u)].color = 'blue'

	def mst_P(self):
		for v in self.V:
			v.pred = None
		r = self.V[0]
		r.key = 0
		Q = FibHeap()
		Q.buildFromVertices(self.V)
		while len(Q) > 0:
			minNode = Q.extractMin()
			u = minNode.pointer
			u.mark = True
			for v in u.adj:
				if v.mark == False:
					if self.E[(u,v)].w < v.key:
						Q.decreaseKey(v.key, self.E[(u,v)].w, node = v.pTreeNode)
						v.key = self.E[(u,v)].w
						v.pred = u
		for v in self.V:
			u = v.pred
			if u != None:
				self.E[(u,v)].color = self.E[(v,u)].color = 'blue' 

	def shortestPath_BellmanFord_SC(self, start=None):
		for v in self.V:
			v.key = INF
			v.pred = None
		if start == None:
			start = self.V[0]
		start.key = 0
		# self.sp = dict()
		# self.sp[(start, start)] = [start]
		for i in range(len(self.V)-1):
			for e in self.E:
				u, v = e[0], e[1]
				if v.key > u.key + self.E[e].w:
					v.key = u.key + self.E[e].w
					v.pred = u
					# self.sp[(start,v)] = self.sp[(start,u)] + [v]
		for v in self.V:
			v.content = v.content + ':' + str(v.key)
		start.pred = None
		if self._noNegativeCycle():
			return True
		
	def shortestPath_Dijkstra(self, start=None):
		for v in self.V:
			v.key = INF
			v.pred = None
		if start == None:
			start = self.V[0]
		start.key = 0
		Q = FibHeap()
		Q.buildFromVertices(self.V)
		while len(Q) > 0:
			minNode = Q.extractMin()
			u = minNode.pointer
			for v in u.adj:
				e = self.E[(u,v)]
				if v.key > u.key + e.w:
					Q.decreaseKey(v.key, u.key + e.w, node = v.pTreeNode)
					v.key = u.key + e.w
					v.pred = u
		for v in self.V:
			v.content = v.content + ':' + str(v.key)

	def shortestPath_DFS_singleSource(self, start=None):
		topoSorted = self.DFS_singleSource(start)
		for v in topoSorted:
			v.key = INF
			v.pred = None
		start = topoSorted[0]
		start.key = 0
		for u in topoSorted:
			for v in u.adj:
				edge = self.E[(u,v)]
				if v.key > u.key + edge.w:
					v.key = u.key + edge.w
					v.pred = u
		for v in topoSorted:
			v.content = v.content + ':' + str(v.key)

	def findSHP_uv(self, u, v):
		if self._noNegativeCycle():
			u.color = v.color = 'gray'
			while v.pred != None and v != u:
				self.E[(v.pred,v)].color = 'blue'
				self.E[(v.pred,v)].thickness = 3
				# print((v.pred.ID, v.ID, self.E[(v.pred,v)].w),end=',')
				v = v.pred
		else:
			u.color = v.color = 'blue'
			sp = self.sp[(u,v)]
			# for x in sp:
			# 	print(x.ID, end=',')
			i = 0
			while i+1 < len(sp):
				self.E[(sp[i],sp[i+1])].color = 'blue'
				self.E[(sp[i],sp[i+1])].thickness = 3
				i += 1

	def _noNegativeCycle(self):
		for e in self.E:
			edge = self.E[e]
			u, v = e[0], e[1]
			if v.key > u.key + edge.w:
				edge.color = 'green'
				return False
		return True

	def AP_shortestPath_DP(self):
		N = len(self.V)
		w = self.adjMT
		p = self.predMT
		mt1 = np.copy(w)
		mt2 = np.copy(w)
		step = 1
		while step < N-1:
			for i in range(N):
				for j in range(N):
					for k in range(N):
						if k == i or k == j:
							pass
						elif mt2[i,j] > mt1[i,k] + mt1[k,j]:
							mt2[i,j] = mt1[i,k] + mt1[k,j]
							p[i,j] = k
			mt1 = np.copy(mt2)
			step *= 2
		return mt1

	def AP_SP_Floyd_Warshall(self):
		N = len(self.V)
		w = self.adjMT
		p = self.predMT
		mt = np.copy(w)
		for k in range(N):
			for i in range(N):		
				for j in range(N):		
					if mt[i,j] > mt[i,k] + mt[k,j]:
						mt[i,j] = mt[i,k] + mt[k,j]
						p[i,j] = k
		return mt

	def showSHP(self, u, v):
		if isinstance(u, Vertice):
			u, v = u.ID, v.ID
		p = self.predMT
		if p[u, v] == INF:
			print('no path')
			return False
		else:
			path = [v]
			while p[u,v] != u:
				path.insert(0, p[u,v])
				v = p[u,v]
			path.insert(0, u)
			print(path)
			return path

	def Ford_Fulkerson(self):
		toRestore = {}
		for k,v in zip(self.E.keys(), self.E.values()):
			toRestore[k] = v
		augPath = self._getAugPath() 
		while augPath is not None:
			minV = min(augPath, key=lambda e: e.r).r
			for e in augPath:
				e.f += minV
				e.r -= minV
				u, v = e.pair
				if e.r == 0:
					self.E.pop((u,v))
					u.adj.remove(v)
				if (v,u) not in self.E:
					self.E[(v,u)] = Edge((v,u))
					self.E[(v,u)].r = 0
					v.adj.append(u)
				self.E[(v,u)].r += minV
			augPath = self._getAugPath() 
		self.rE = self.E
		self.E = toRestore
		for u,v in self.E:
			e = self.E[(u,v)]
			if (u,v) in self.rE:
				re = self.rE[(u,v)]
				e.w = str(re.f) + '/' + str(re.c)  
			else:
				e.f = e.c
				e.w = str(e.f) + '/' + str(e.c)  

	def _getAugPath(self):
		augPath = []
		self.BFS(self.source.ID)
		if self.sink in self.source.linkedV:
			v = self.sink
			while v.pred is not None:
				u = v.pred
				e = self.E[(u,v)]
				augPath.insert(0, e)
				v = u
			return augPath
		else:
			return None


class DisjointSet(object):
	def __init__(self, node):
		super().__init__()
		self.rank = 0
		self.rep = self
		self.pNode = node
	
	def union(self, other):
		x, y = self.rep, other.rep
		if x.rank < y.rank:
			x.rep = y
			self.updateRep()
		else:
			y.rep = x
			other.updateRep()
			if x.rank == y.rank:
				x.rank += 1

	def updateRep(self):
		if self.rep != self:
			self.rep = self.rep.updateRep()
		return self.rep

class SingletonINF(int):
	_instance = None
	def __new__(cls):
		if cls._instance == None:
			cls._instance = int.__new__(cls, INF)
		return cls._instance
	def __add__(self, b):
		return self
	def __sub__(self, b):
		if b is not self:
			return self
		else: return 0
	def __mul__(self, b):
		return self

def test():
	# g.randomGraph(6,13) seed: 17 18 20 25
	# g.randomGraph(6,13)
	# g.randomGraph(6,15)
	# draw = DrawGraph(g)
	g = Graph(directG=True)
	# g.randomGraph(6,15, seed=20)	
	g.randomGraph_MF(6,11, seed=16)	
	draw = DrawGraph(g)
	g.Ford_Fulkerson()
	draw = DrawGraph(g)


	# g.DFS()
	# draw = DrawGraph(g)
	# g.scc()
	# draw = DrawGraph(g)
	# frt = g.graph2Forest()
	# draw = DrawForest(frt)
	# g.BFS(7)
	# draw = DrawGraph(g)
	# t = g.graph2Tree(7)
	# d2 = DrawTreeByLink(t)
	# g.mst_K()
	# g.mst_P()
	# g.shortestPath_BellmanFord_SC(start=g.V[1])
	# # g.findSHP_uv(g.V[1],g.V[3])
	# g.shortestPath_Dijkstra(start=g.V[1])
	# g.findSHP_uv(g.V[1],g.V[3])
	# g.shortestPath_Dijkstra(start=g.V[2])
	# g.findSHP_uv(g.V[2],g.V[5])
	# draw = DrawGraph(g)
	# t = g.graph2Tree(g.V[1].ID)
	# draw = DrawTreeByLink(t)
	# print(g.noNegativeCycle())
	# draw = DrawGraph(g)
	# g.convert()
	# print(g.adjMT)
	# g.E.clear()
	# g.convert()
	# for e in g.E.values():
	# 	print(e)
	# frt = g.DFS()
	# draw._redraw()
	# draw = DrawForest(frt)
	# g.shortestPath_Dijkstra(start=g.V[2])
	# g.findSHP_uv(g.V[2],g.V[5])
	# draw = DrawGraph(g)
	# g.DFS_singleSource(g.V[1])
	# g.shortestPath_DFS_singleSource(start=g.V[1])
	# g.findSHP_uv(g.V[1],g.V[3])
	# draw = DrawGraph(g)
	# g.shortestPath_Dijkstra(start=g.V[3])
	# g.findSHP_uv(g.V[3],g.V[4])
	# draw = DrawGraph(g)
	# g.convert()
	# apshp = g.AP_shortestPath_DP()
	# apshp = g.AP_SP_Floyd_Warshall()
	# print(apshp)
	# print(g.predMT)
	# g.showSHP(3,4)


test()
		




